﻿#define  _CRT_SECURE_NO_WARNINGS
//来个单链表的交汇（相交问题）   力扣选题
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始
//节点。如果两个链表不存在相交节点，返回 null


//思路：先遍历到尾部看尾部是否相等，
//     再如果相交，就找交点：看地址，不能看其对应的值
//  两个节点不同但其对应的值是相等的，不能说明就是同一个节点，但如果对应的地址相等就说明指向的是同一个节点
//              1.分别逐个遍历，并且找地址相等的点  复杂度O（N^2）
//              2.算出两个链表的距离差，让长的链表先走距离差个节点，再让两个链表同时遍历，直到遇到地址相同的节点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct ListNode {
	int val;
	struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
	struct ListNode* curA = headA, * curB = headB;
	int lenA = 0;
	int lenB = 0;
	//判断两个链表是否相交
	while (curA)
	{
		curA = curA->next;
		lenA++;
	}
	while (curB)
	{
		curB = curB->next;
		lenB++;
	}
	if (curA != curB)
		return NULL;
	//让先走距离差个节点
	int gap = abs(lenA - lenB);
	//在这里我们并不知道哪个是长链表，我们使用假设法

	struct ListNode* longlist = headA, * shortlist = headB;
	if (lenA < lenB)
	{
		longlist = headB;
		shortlist = headB;
	}
	while (gap--)
	{
		longlist = longlist->next;
	}
	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	return shortlist;
}
void print(struct ListNode*plist)
{
	assert(plist);
	while (plist)
	{
		printf("%d->", plist->val);
		plist = plist->next;
	}
	printf("NULL\n");
}
struct ListNode * sltbuynode(int x)
{
	struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
void sltpushback(struct ListNode** pphead, int x)
{
	assert(pphead);
	//创建新节点
	struct ListNode* newnode = sltbuynode(x);
	//在尾插的时候分为两种情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		struct ListNode* cur = *pphead;
		while (cur->next!=NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
int main()
{
	    struct ListNode * node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
		node1->val = 1;
		struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
		node2->val = 2;
		struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
		node3->val = 3;
		struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
		node4->val = 4;
		struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
		node5->val = 5;
	
	
		//将四个节点连接起来
		node1->next = node2;
		node2->next = node4;
		node3->next = node4;
		node4->next = node5;

		node5->next = NULL;
	
	//创建链表
	struct ListNode* headA = node1;
	struct ListNode* headB = node3;
	//尾插
	/*sltpushback(&headA,1);
	sltpushback(&headA,2);
	sltpushback(&headA,3);
	sltpushback(&headA,4);
	sltpushback(&headA,5);
	
	sltpushback(&headB,6);
	sltpushback(&headB,7);
	sltpushback(&headB,8);
	sltpushback(&headB,3);
	sltpushback(&headB,4);
	sltpushback(&headB,5);*/

	//打印两个链表
	print(headA);
	print(headB);
	struct ListNode * ret=getIntersectionNode(headA, headB);
	if (ret == NULL)
		printf("NULL\n");
	print(ret);
	return 0;
}